package array;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * @author yuisama
 * @date 2022/08/23 10:09
 * 数组练习
 **/
public class ArrayPractice {
//    public static void main(String[] args) {
        // 自己实现的全拷贝
//        int[] arr1 = copyOf(arr);
//        arr1[1] = 30;
//        System.out.println(arr2Str(arr1));
//        System.out.println(arr2Str(arr));
//        // JDK的数组拷贝
//        // 第一个参数要拷贝的数组名称，拷贝的长度
//        int[] arr1 = Arrays.copyOf(arr,arr.length);
//        // [)
//        int[] arr2 = Arrays.copyOfRange(arr,2,4);
//        System.out.println(arr2Str(arr1));
//        System.out.println(arr2Str(arr2));
//        // JDK内置的将数组对象转为字符串
//        System.out.println(Arrays.toString(arr));
//        // 自己实现的数组转字符串操作
//        System.out.println(arr2Str(arr));
//        int[] arr = {1,3,4,5,7,10,11,12,15,19,20,30,100};
//        System.out.println(find(arr,15));
//        System.out.println(binSearch(arr,15));
//        System.out.println(binSearchRecursion(arr,0,arr.length - 1,15));
//        int[] arr = {1,3,5,7,9};
////        // println函数内部必须传一个值，void方法来说压根就没有返回值，不能将void方法直接传递给println方法
////        System.out.println(reverse(arr));
//        reverse(arr);
//        System.out.println(arr2Str(arr));
//        int[] arr = {3,1,2,9,5,6,7,4,10};
//        bubbleSort(arr);
//        System.out.println(arr2Str(arr));
//    }

    public static void bubbleSort(int[] arr) {
        // 最开始时 :
        // 无序区间[0...arr.length - 1]
        // 有序区间[]
        // 外层循环表示无序区间的个数[0....N],每次进行一次外层循环，最终将一个元素放在了最终的位置
        // 无序区间个数 - 1，有序区间个数 + 1
        // 当外层循环只剩一个元素的时候，无序区间[1] 有序区间[n-1] =》 其实数组已经有序 [1] [2,3,4,5,6,7]
        for (int i = 0; i < arr.length - 1; i++) {
            // 引入标志位，判断内存循环到底是否有元素交换
            boolean isSwap = false;
            // 内层循环就是两两比较元素，若前一个元素 > 后一个元素，交换他俩的位置
            // 每当进行一次内层循环，就将无序区间的最大值放在了数组的末尾，有序区间元素 + 1
            // 不断重复此过程，直到整个数组有序
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    isSwap = true;
                    // 前一个元素 > 后一个元素
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
            // ----- 外层，若内层循环走完，还没有元素交换，终止整个循环，此时整个数组已经有序
            if (!isSwap) {
                break;
            }
        }
    }

    // 如何判断一个数组是一个有序数组(默认升序)?  =》 证伪操作，找反例
    // 判断 XXXX 是否为true，找个反例，能找到false，找不到就是true
    // [1,2,3,4,5,6] true
    // [1,3,2,4,5,6] false
    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 不断比较当前元素是否一定严格小于后一个元素，找反例
            if (arr[i] > arr[i + 1]) {
                // 找到反例
                return false;
            }
        }
        return true;
    }



    public static void reverse(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left ++;
            right --;
        }
    }

    /**
     * 在arr[left...right]查找元素toFind，并返回其索引下标
     * @param arr
     * @param left
     * @param right
     * @param toFind
     * @return
     */
    public static int binSearchRecursion(int[] arr,int left,int right,int toFind) {
        // 1.边界
        if (left > right) {
            return -1;
        }
        int mid = left + ((right - left) >> 1);
        if (arr[mid] == toFind) {
            return mid;
        }else if (toFind < arr[mid]) {
            // 交给子函数在左半区间接着查找
            return binSearchRecursion(arr,left,mid - 1,toFind);
        }
        // 在右半区间查找
        return binSearchRecursion(arr,mid + 1,right,toFind);
    }

    /**
     * 要想使用二分查找，arr必须是个有序数组
     * @param arr
     * @param toFind
     * @return
     */
    public static int binSearch(int[] arr,int toFind) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + ((right -left) >> 1);
            if (toFind < arr[mid]) {
                // 此时接着在左半区间查找
                right = mid - 1;
            }else if (toFind > arr[mid]) {
                // 接着在右半区间查找
                left = mid + 1;
            }else {
                return mid;
            }
        }
        // 此时若在数组压根没找到toFind时，就可以抛出异常，比特定的返回值更加有意义的！
        // -1也有可能是要查找的值，给任何值都不合适，toFind有可能为任何的数值
        throw new NoSuchElementException("在当前数组中没有找到该值！");
    }

    public static void main(String[] args) {
        int[] arr = {-7,-3,-1,0,4,7,9};
        System.out.println(binSearch(arr,-1));
        // 找不到就抛出异常
        System.out.println(binSearch(arr,-10));
    }



    // 练习4.给定一个数组和需要查找的元素，若在该数组中找到指定元素，返回对应的索引下标
    // 若没找到，返回 -1，说明数组中没有要查找的元素
    // [1,3,4,5,7,10,11,12,15,19,20,30,100] 要查找15，若找到返回15对应的数组下标，若找不到返回-1
    // 从前到后遍历这个数组，若在遍历过程中找到了待查找元素，返回对应的索引下标
    // 若整个数组遍历完之后，还没找到待查找的元素，这个元素压根就在数组中不存在，返回-1
    public static int find(int[] arr,int toFind) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == toFind) {
                // 找到元素
                return i;
            }
        }
        return -1;
    }



    // 练习3.计算传入数组的平均值
    public static double avg(int[] arr) {
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        return sum / (arr.length * 1.0);
    }

    /**
     * 对arr数组进行全拷贝
     * @param arr
     * @return
     */
    public static int[] copyOf(int[] arr) {
        int[] ret = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ret[i] = arr[i];
        }
        return ret;
    }

    // 1.练习1，自己实现类似JDK的数组转字符串操作,实际上就是遍历数组，通过字符串的拼接操作而已
    public static String arr2Str(int[] arr) {
        String ret = "[";
        for (int i = 0; i < arr.length; i++) {
            ret += arr[i];
            // 什么时候才需要加,分隔，最起码当前遍历的元素之后还有元素，才需要分隔
            // 此时i还没有走到最后一个数组元素
            if (i < arr.length - 1) {
                ret += ", ";
            }
        }
        ret += "]";
        return ret;
    }

}